package com.ming.learn.from.carl.stack.and.queue;

import java.util.Stack;

/*
232. 用栈实现队列
 */
public class Of20210101LeetCode232 {
    /*
    使用栈实现队列的下列操作：
    push(x) -- 将一个元素放入队列的尾部。
    pop() -- 从队列首部移除元素。
    peek() -- 返回队列首部的元素。
    empty() -- 返回队列是否为空。
     */
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        queue.push(1);
        queue.push(2);
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.empty());
    }

}

/*
思路：
使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈「一个输入栈，一个输出栈」，这里要注意输入栈和输出栈的关系。
在push数据的时候，只要数据放进输入栈就好，「但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入）」，再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
 */
class MyQueue {
    Stack<Integer> stIn = new Stack<>();
    Stack<Integer> stOut = new Stack<>();

    void push(int x) {
        stIn.push(x);
    }

    int pop() {
        if (stOut.empty()) {
            while (!stIn.empty()) {
                stOut.push(stIn.pop());
            }
        }
        return stOut.pop();
    }

    int peek() {
        int pop = pop();
        stOut.push(pop);
        return pop;
    }

    boolean empty() {
        return stIn.empty() && stOut.empty();
    }
}
